package com.yoshino.leetcode.interview150.dictTree;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        WordTrie trie = new WordTrie();
        TrieNode root = trie.root;
        // 插入数据
        for (String word : words) {
            trie.insert(word);
        }
        List<String> res = new ArrayList<>();
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                find(board, visited, i, j, m, n, res, root);
            }
        }
        return res;
    }

    private void find(char[][] board, boolean[][] visited, int i, int j, int m, int n, List<String> res, TrieNode cur) {
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j]) {
            // 无效
            return;
        }
        cur = cur.child[board[i][j] - 'a'];
        if (cur == null) {
            return;
        }
        visited[i][j] = true;
        if (cur.val != null) {
            // 有值
            res.add(cur.val);
            // 已加入的，重置为 null，防止重复
            cur.val = null;
        }
        find(board, visited, i + 1, j, m, n, res, cur);
        find(board, visited, i - 1, j, m, n, res, cur);
        find(board, visited, i, j + 1, m, n, res, cur);
        find(board, visited, i, j - 1, m, n, res, cur);
        visited[i][j] = false;
    }

    /**
     * 字典树
     */
    class WordTrie {
        //创建根节点
        TrieNode root = new TrieNode();

        void insert(String s) {
            TrieNode cur = root;
            for (char c : s.toCharArray()) {
                //判断是否存在该字符的节点，不存在则创建
                if (cur.child[c - 'a'] == null) {
                    cur.child[c - 'a'] = new TrieNode();
                }
                cur = cur.child[c - 'a'];
            }
            //遍历结束后，修改叶子节点的状态，并存储字符串
            cur.val = s;
        }
    }

    /**
     * 字典树节点
     */
    class TrieNode {
        /**
         * 存储最后节点的字符串
         */
        String val;
        /**
         * 根据字符排序，[a,b,c,……,z]
         */
        TrieNode[] child = new TrieNode[26];
    }
}